Sebelum pengendalian surat penjajahan dimulakan pada tahun 1809, surat biasanya diserahkan oleh pengaturan ad hoc yang dibuat antara pengangkut, penjaga kedai dan peneroka. Pengaturan ini fleksibel dan bergantung pada kerjasama rakyat negara ini. Adalah lumrah bagi para peneroka awal untuk menempuh jarak jauh lebih jauh dari jalan mereka untuk menghantar surat jiran yang telah dikumpulkan dari tempat pengedaran tidak rasmi.[5]

Pertubuhan pertama perkhidmatan pos di Australia bermula pada tahun 1809 dengan pelantikan di Sydney pertama Postmaster of New South Wales. Dia adalah seorang Inggeris bekas banduan, Isaac Nichols, yang mengambil jawatan itu beroperasi dari rumahnya di George Street, Sydney. Tugas utamanya adalah mengurus surat dan bungkusan yang tiba dengan kapal, untuk mengelakkan kekacauan orang yang bergegas ke kapal sebaik sahaja mereka tiba di dermaga Sydney. Nichols akan mengambil surat dan menyiarkan senarai penerima di luar rumahnya.[6] Dia akan mengiklankan di Sydney Gazette nama-nama semua orang yang menerima surat. Penerima membayar harga tetap satu shilling per surat untuk mengambil surat dari rumah Nichols, dengan bungkusan berharga lebih banyak bergantung pada berapa beratnya. VIP penerima diberi penghantaran peribadi oleh Nichols.[7]

Undang-undang Pos pada tahun 1825 membenarkan gabenor menetapkan kadar pos dan melantik tuan pos di luar Sydney, yang membolehkan perkhidmatan pos yang teratur.[8] Penghantaran surat bermula pada tahun 1828 dan kotak pengeposan pertama kali muncul pada tahun 1831.[7] Setem tidak diperlukan pada masa itu, kerana penerima membayar surat itu, bukan pengirimnya.[7]

Perkhidmatan pos berkembang di seluruh jajahan Australia ketika mereka ditubuhkan. Perkhidmatan darat biasa antara Sydney dan Melbourne, Port Phillip District bermula pada tahun 1838.[9] Juga pada tahun 1838, lembaran surat "dicop" prabayar pertama diperkenalkan di Sydney.[7] Menjelang tahun 1849, kadar pos seragam ditetapkan dengan persetujuan antara jajahan. Setem pelekat prabayar diperkenalkan pada tahun 1850-an. Victoria adalah yang pertama membuat bayaran pendahuluan dengan setem pada tahun 1852.[7] Surat kapal laut bulanan ke United Kingdom ditubuhkan pada tahun 1856. Jajahan yang terpisah bergabung dengan Universal Postal Union pada tahun 1891.

Setelah persekutuan pada tahun 1901, sistem surat kolonial digabungkan ke dalam Postmaster-General's Department (PMG). Badan ini bertanggungjawab untuk operasi telegraf dan telefon domestik dan juga pos. Perkhidmatan pos udara diperkenalkan pada tahun 1914.[7] Sistem penyortiran surat mekanikal berskala besar pertama di dunia diperkenalkan di Australia (menurut Australia Post),[petikan diperlukan] dan beroperasi di Sydney GPO pada tahun 1967 Ini bertepatan dengan pengenalan sistem terkini 4 digit poskod di Australia.[10]

Pada 1 Julai 1975, komisen pemerintah yang terpisah telah dibuat untuk menjalankan tanggungjawab operasi PMG. Salah satunya adalah Suruhanjaya Pos Australia, yang diperdagangkan sebagai Australia Post. Ia kemudian menjadi Australian Postal Corporation pada 1 Januari 1989 ketika ia diperbadankan. Ia terus diperdagangkan sebagai Australia Post.

Di bawah pindaan terhadap Akta APC yang mulai berlaku pada bulan Mac 2008, pegawai pemeriksaan karantina dari sebuah negeri atau wilayah diberi wewenang untuk meminta Australia Post untuk membuka paket pemeriksaan dan bungkusan yang dikirim dari interstate yang mereka percaya mungkin mengandung bahan karantina. Perundangan ini juga mengizinkan Australia Post untuk menghapus dari artikel surat yang disyaki sebagai surat penipuan.[11]

Ulang tahun ke-200 perkhidmatan pos disambut pada tahun 2009.[11]